// 定义链表节点类
class ListNode {
    int val;
    ListNode next;

    ListNode() {}

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Main {
    public static void main(String[] args) {
        // 创建链表节点
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        // 连接链表节点
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        // 可以通过node1来访问整个链表

        reorderList(node1);
    }

    public static void reorderList(ListNode head) {
        // 处理边界情况(少于两个节点时，无需去重排)
        if (head == null || head.next == null || head.next.next == null) {
            return;
        }
        // 1、先找到中间结点
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 2、将 slow 后面的结点进行逆序
        ListNode cur = slow.next;
        slow.next = null; // 分割成两个链表
        ListNode next = cur.next, prev = null;
        while (cur != null) {
            // 修改指针指向
            cur.next = prev;
            // 更新指针
            prev = cur;
            cur = next;
            next = next == null ? null : next.next;
        }
        // 3、合并两个链表
        cur = head;
        ListNode newHead = new ListNode(-1), ret = newHead;
        while (prev != null) { // 这里一定是逆序链表先遍历完成
            // 先插入原链表节点
            ret.next = cur;
            // 更新指针（原链表、新链表）
            ret = cur;
            cur = cur.next;
            // 再插入逆序链表节点
            ret.next = prev;
            // 更新指针(逆序链表、新链表)
            ret = prev;
            prev = prev.next;
        }
        // 将原链表后的结点插入新链表即可
        ret.next = cur;
        head = newHead.next;
    }
}